package cn.kent.simple;

import javafx.scene.effect.Blend;

import java.util.ArrayDeque;
import java.util.HashMap;

/**
 * 496. 下一个更大元素 I
 * <p>
 * nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
 * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
 * 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
 * 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
 * <p>
 * 输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
 * 输出：[-1,3,-1]
 * 解释：nums1 中每个值的下一个更大元素如下所述：
 * - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
 * - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
 * - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
 */
public class NextGreaterElement {
    public static void main(String[] args) {
        int[] nums1 = {4, 1, 2};
        int[] nums2 = {1, 3, 4, 2};
        int[] ints = nextGreaterElement2(nums1, nums2);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

    /**
     * 单调栈+哈希表
     */
    public static int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        // 新建栈存储下一个元素是大值
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        // 先处理nums2，将nums2的符合条件的下一最大值放到stack中
        for (int i = nums2.length-1; i >= 0; --i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        // 最后一次循环处理
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }

    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        for (int n = 0; n < nums1.length; n++) {
            fn:
            for (int i = 0; i < nums2.length; i++) {
                if (nums2[i] == nums1[n]) {
                    for (int j = i + 1; j < nums2.length; j++) {
                        if (nums2[j] > nums1[n]) {
                            res[n] = nums2[j];
                            break fn;
                        }
                    }
                    res[n] = -1;
                    break;
                }
            }
        }
        return res;
    }
}
